package org.example.myleet.p981;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class TimeMap {

    static class TimeValue {
        int timestamp;
        String value;

        public TimeValue(int timestamp, String value) {
            this.timestamp = timestamp;
            this.value = value;
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("TimeValue{");
            sb.append("timestamp=").append(timestamp);
            sb.append(", value='").append(value).append('\'');
            sb.append('}');
            return sb.toString();
        }
    }

    private Map<String, List<TimeValue>> map;

    /** Initialize your data structure here. */
    public TimeMap() {
        map = new HashMap<>();
    }

    public void set(String key, String value, int timestamp) {
        List<TimeValue> values = map.getOrDefault(key, new ArrayList<>());
        values.add(new TimeValue(timestamp, value));
        map.put(key, values);
    }

    public String get(String key, int timestamp) {
        List<TimeValue> values = map.getOrDefault(key, new ArrayList<>());
        if (values.size() < 1 || timestamp < values.get(0).timestamp) {
            //找不到values或所查询时间戳小于最小的timestamp，即认为找不到
            return "";
        }
        if (timestamp >= values.get(values.size() - 1).timestamp) {
            //所查询时间戳大于最大的timestamp，则直接返回最大的timestamp的值
            return values.get(values.size() - 1).value;
        }
        //所查询时间戳处于整个时间序列中间，使用二分法找到最接近的时间戳
        int l = 0, r = values.size() - 1;
        while (r - l > 1) {
            int mid = (r + l) / 2;
            TimeValue value = values.get(mid);
            if (value.timestamp == timestamp) {
                return value.value;
            } else if (value.timestamp > timestamp) {
                r = mid;
            } else {
                l = mid;
            }
        }
        TimeValue rValue = values.get(r);
        if (rValue.timestamp <= timestamp) {
            return rValue.value;
        }
        return values.get(l).value;
    }
}
